package com.asia.algorithmcode.backTracking;

import java.util.Arrays;

/**
 * @DESCRIPTION:
 * @USER: wanfu
 * @DATE: 2025/3/25 星期二 17:11
 */
public class Exist {

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        System.out.println(new Exist().exist(board, "ABCCSES"));

    }


    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] used = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (check(board, used, i, j, 0, word)) {
                    return true;
                }
            }
        }

        return false;
    }

    // 需要能从一个位置出发寻找到相邻位置是否能够匹配当前字符,能够完成匹配的唯一情况就是匹配的位置到字符串的最后一个字符
    private boolean check(char[][] board, boolean[][] used, int i, int j, int k, String word) {
        // 递归出口
        if (word.charAt(k) != board[i][j]) {
            return false;
        } else if (k >= word.length() - 1) {
            return true;
        }

        boolean flag = false;
        used[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};


        for (int[] direction : directions) {
            int m = i + direction[0];
            int n = j + direction[1];
            if (m < 0 || n < 0 || m >= board.length || n >= board[0].length) {
                continue;
            }
            if (!used[m][n]) {
                boolean innerFlag = check(board, used, m, n, k + 1, word);
                if (innerFlag) {
                    flag = true;
                    break;
                }
            }
        }
        used[i][j] = false;

        return flag;
    }


}
